class Solution
{
public:
    long long countPrefixSuffixPairs(vector<string> &words)
    {
        unordered_set<int> wordSizes;
        for (auto &word : words)
        {
            wordSizes.insert(word.size());
        }

        unordered_map<string_view, int> prefixSuffixs;
        long long result = 0;
        for (auto it = words.rbegin(); it != words.rend(); ++it)
        {
            string_view word = *it;
            if (prefixSuffixs.count(word))
            {
                result += prefixSuffixs[word];
            }

            int n = word.size();
            vector<int> next(n, -1);
            for (int i = 1, j = -1; i < n; i++)
            {
                while (j != -1 && word[i] != word[j + 1])
                {
                    j = next[j];
                }
                if (word[i] == word[j + 1])
                {
                    j++;
                }
                next[i] = j;
            }

            int j = n - 1;
            while (j != -1)
            {
                if (wordSizes.count(j + 1))
                {
                    prefixSuffixs[word.substr(0, j + 1)]++;
                }

                j = next[j];
            }
        }
        return result;
    }
};